#include <bits/stdc++.h>

using namespace std;

class Solution
{
    static bool flag;
    static vector<long long> targetNums;
    void getPermu(string &curPerm, map<char, int> &counts, int totalLen, const string &center)
    {
        if (curPerm.length() == totalLen)
        {
            string right = curPerm;
            reverse(right.begin(), right.end());
            string pStr = curPerm + center + right;
            try
            {
                if (pStr.length() <= 16)
                    targetNums.push_back(stoll(pStr));
            }
            catch (...)
            {
            }
            return;
        }

        for (auto const &[digit, count] : counts)
        {
            if (count > 0)
            {
                if (curPerm.empty() && digit == '0')
                    continue;

                curPerm.push_back(digit);
                counts[digit]--;
                getPermu(curPerm, counts, totalLen, center);
                counts[digit]++;
                curPerm.pop_back();
            }
        }
    }
    void precompute()
    {
        if (flag || !targetNums.empty())
            return;
        flag = true;
        vector<int> ODD = {1, 3, 5, 7, 9};
        vector<int> EVEN = {2, 4, 6, 8};

        for (int i = 0; i < (1 << EVEN.size()); ++i)
        {
            // 1. 只包含偶数次计数的数字
            {
                map<char, int> counts;
                int half_len = 0;
                int total_len_sum = 0;
                for (int j = 0; j < EVEN.size(); ++j)
                {
                    if ((i >> j) & 1)
                    {
                        total_len_sum += EVEN[j];
                    }
                }
                // 剪枝：如果总长度会超过16，则跳过这个组合
                if (total_len_sum > 0 && total_len_sum <= 16)
                {
                    for (int j = 0; j < EVEN.size(); ++j)
                    {
                        if ((i >> j) & 1)
                        {
                            counts[EVEN[j] + '0'] = EVEN[j] / 2;
                            half_len += EVEN[j] / 2;
                        }
                    }
                    string p = "";
                    getPermu(p, counts, half_len, "");
                }
            }

            // 2. 包含一个奇数次计数的数字和若干偶数次计数的数字
            for (int odd_d : ODD)
            {
                map<char, int> counts;
                int half_len = 0;
                int total_len_sum = odd_d;

                for (int j = 0; j < EVEN.size(); ++j)
                {
                    if ((i >> j) & 1)
                    {
                        total_len_sum += EVEN[j];
                    }
                }

                if (total_len_sum > 16)
                    continue;

                for (int j = 0; j < EVEN.size(); ++j)
                {
                    if ((i >> j) & 1)
                    {
                        counts[EVEN[j] + '0'] = EVEN[j] / 2;
                        half_len += EVEN[j] / 2;
                    }
                }

                // 添加奇数次计数的数字
                counts[odd_d + '0'] = (odd_d - 1) / 2;
                half_len += (odd_d - 1) / 2;

                string center = to_string(odd_d);
                string p = "";
                getPermu(p, counts, half_len, center);
            }
        }

        // 3. 只有一个奇数次计数数字的情况
        for (int d : ODD)
        {
            // 长度 d 本身不能超过16
            if (d <= 16)
            {
                string s(d, d + '0');
                targetNums.push_back(stoll(s));
            }
        }

        sort(targetNums.begin(), targetNums.end());
        targetNums.erase(unique(targetNums.begin(), targetNums.end()), targetNums.end());
    }

public:
    long long specialPalindrome(long long n)
    {
        precompute();
        auto it = upper_bound(targetNums.begin(), targetNums.end(), n);
        return *it;
    }
};

bool Solution::flag = false;
vector<long long> Solution::targetNums = {};